#include <string.h>
#include "../include/map.h"
#include "../include/string.h"
#include "../include/line.h"

#define OVERFLOWER_SIZE(map) ((map)->size / 4u)

u_int Map_GetHashCode(const TValue *value)
{
    if (value->category == T_STRING)
    {
        return ((String *)value->value.object)->hashCode;
    }
    return value->value.integer;
}

void Map_resize(Map *self, u_int size)
{
    Map map = {.array = self->array, .size = self->size, .overflow = self->overflow};

    if (size == 0)
    {
        self->size = 0;
        self->array = NULL;
        self->overflow = NULL;
    }
    else
    {

        self->size = size;
        self->array = Globe_Malloc(sizeof(MapNode) * (self->size + self->size / 4));
        self->overflow = &self->array[self->size];
        Map_Clear(self);
        for (u_int i = 0; i < map.size; i++)
        {
            MapNode *node = &map.array[i];
            while (node != NULL && node->value.category != T_NULL)
            {
                Map_Put(self, node->key, node->value);
                if (node->next == OVERFLOWER_SIZE(&map))
                    break;
                node = &map.overflow[node->next];
            }
        }
        Globe_Free(map.array);
    }
}

void Map_Clear(Map *self)
{
    for (u_int i = 0; i < self->size; i++)
    {
        self->array[i].value = TNULL;
        self->array[i].next = OVERFLOWER_SIZE(self);
    }
    for (u_int i = 0; i < self->size / 4; i++)
    {
        self->overflow[i].next = i + 1;
    }
    self->overflow[self->size / 4 - 1].next = OVERFLOWER_SIZE(self);
    self->freeNode = 0;
    self->length = 0;
}

void Map_Init(Map *self, u_int size)
{
    if ((size & (size - 1)) != 0)
    {
        printf("初始大小必须为2的N次方");
        exit(0);
    }
    self->type = T_MAP;
    self->size = 0;
    self->array = NULL;
    self->overflow = NULL;
    self->freeNode = OVERFLOWER_SIZE(self);
    Map_resize(self, size);
}

void Map_Put(Map *self, TValue key, TValue value)
{
    if (key.category != T_STRING && key.category != T_INTEGER)
    {
        return;
    }
    if (value.category == T_NULL)
    {
        Map_Remove(self, key);
        return;
    }
    if (self->freeNode == OVERFLOWER_SIZE(self))
        Map_resize(self, self->size << 1);
    u_int index = Map_GetHashCode(&key) & (self->size - 1);
    MapNode *node = &self->array[index];
    if (node->value.category == T_NULL)
    {
        node->key = key;
        node->value = value;
    }
    else
    {
        while (true)
        {
            if (TValue_Equals(&node->key, &key))
            {
                node->value = value;
                return;
            }
            if (node->next == OVERFLOWER_SIZE(self))
                break;
            node = &self->overflow[node->next];
        };
        node->next = self->freeNode;
        node = &self->overflow[self->freeNode];
        self->freeNode = node->next;
        node->next = OVERFLOWER_SIZE(self);
        node->key = key;
        node->value = value;
    }
    self->length++;
}

TValue Map_Get(Map *self, TValue key)
{
    TValue result = {T_NULL, {}};
    if (key.category != T_STRING && key.category != T_INTEGER)
    {
        return result;
    }
    u_int index = Map_GetHashCode(&key) & (self->size - 1);
    if (self->array == NULL)
    {
        return result;
    }
    MapNode *node = &self->array[index];
    while (true)
    {
        if (TValue_Equals(&node->key, &key))
        {
            result = node->value;
            break;
        }
        if (node->next == OVERFLOWER_SIZE(self))
            break;
        node = &self->overflow[node->next];
    };
    return result;
}

TValue Map_Remove(Map *self, TValue key)
{
    TValue result = {T_NULL, {}};
    if (key.category != T_STRING && key.category != T_INTEGER)
    {
        return result;
    }
    if (self->size > 1024 && self->length < self->size / 4)
    {
        Map_resize(self, self->size >> 1);
    }
    u_int index = Map_GetHashCode(&key) & (self->size - 1);
    MapNode *node = &self->array[index];

    if (TValue_Equals(&node->key, &key))
    {
        if (node->next == OVERFLOWER_SIZE(self))
        {
            result = node->value;
            node->value = TNULL;
            self->length--;
            return result;
        }
        u_int position = node->next;
        *node = self->overflow[position];
        self->overflow[position].next = self->freeNode;
        self->freeNode = position;
    }
    if (node->next == OVERFLOWER_SIZE(self))
        return result;
    MapNode *quick = &self->overflow[node->next];
    do
    {
        if (TValue_Equals(&quick->key, &key))
        {
            u_int position = node->next;
            result = quick->value;
            node->next = quick->next;
            quick->next = self->freeNode;
            self->freeNode = position;
            self->length--;
            return result;
        }
        node = quick;
        quick = &self->overflow[quick->next];
    } while (quick->next != OVERFLOWER_SIZE(self));
    return result;
}

void Delete_Map(Object *self)
{
    Map *map = (Map *)self;
    Globe_Free(map->array);
}

Map *Map_New(Line *line, u_int size)
{
    Map *self = (Map *)Globe_Malloc(sizeof(Map));
    Map_Init(self, size);
    return (Object *)self;
}
